---
title: "4、数的分解"
created: 2025-11-28
tags:
  - 算法
---

# 4、数的分解

## 题目  [数的分解](https://www.lanqiao.cn/paper/3842/problem/606/)

![[image-4f0e6736.png]]

## 思路分析

直接暴力的话 要算几十分钟

```cpp
#include<bits/stdc++.h>

using namespace std;

bool check(string s){

	if(count(s.begin(),s.end(),'2') || count(s.begin(),s.end(),'4'))

		return true;

	return false;

}

int main()

{

    int a, b, c;

    int cnt = 0;

    for(a = 1; a < 2019; a++) {

        int i = a;

        string s = to_string(i);

        if(check(s))

            continue;

        for(b = 1; b < 2019; b++) {

            int j = b;

            string s2 = to_string(j);

            if(check(s2))

                continue;

            for(c = 1; c < 2019; c++) {

                int k = c;

                string s3 = to_string(k);

                if(check(s3))

                    continue;

                if(a!=b && a!=c && b!=c && a+b+c==2019){

                	cnt++;

                	cout<<a<<"+"<<b<<"+"<<c;

                	cout<<endl;

				}

            }

        }

    }

    cout<<cnt/3<<endl;

    return 0;

}
```

优化思路

确定前两个数 第三个数就也确定了（四平方和那题）

重复算同一种 三数不能相同 所以第二层可以从第一层的后一个开始

另外 0~2019 其实可以实现筛出来合法的数

只需要在这些合法的数里面做枚举即可

```cpp
#include<bits/stdc++.h>

using namespace std;

bool check(int num){

	string s=to_string(num);

	if(count(s.begin(),s.end(),'2') || count(s.begin(),s.end(),'4'))

		return false;

	return true;

}

int main()

{

	vector<int> valid;

	for(int i=1;i<2019;i++){

		if(check(i))

			valid.push_back(i);

	}

    int a, b, c;

    int cnt = 0;

    int n=valid.size();

    for(int i = 0; i < n; i++) {

        for(int j = i+1; j < n; j++) {

			a=valid[i],b=valid[j];

           	c=2019-a-b;

           	if(c>b && find(valid.begin(),valid.end(),c)!= valid.end())

               cnt++;

        }

    }

    cout<<cnt<<endl;

    return 0;

}
```

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

bool check(int num){

	string s=to_string(num);

	if(count(s.begin(),s.end(),'2') || count(s.begin(),s.end(),'4'))

		return false;

	return true;

}

int main()

{

	// vector<int> valid;

	// for(int i=1;i<2019;i++){

	// 	if(check(i))

	// 		valid.push_back(i);

	// }

  //   int a, b, c;

  //   int cnt = 0;

  //   int n=valid.size();

  //   for(int i = 0; i < n; i++) {

  //       for(int j = i+1; j < n; j++) {

	// 		a=valid[i],b=valid[j];

  //          	c=2019-a-b;

  //          	if(c>b && find(valid.begin(),valid.end(),c)!= valid.end())

  //              cnt++;

  //       }

  //   }

  //   cout<<cnt<<endl;

    cout<<"40785";

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[3、数列求值|3、数列求值]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/历年真题 模考特训/第十届 c++ B组 省赛/5、迷宫|5、迷宫]]